package com.链表2;

/**
 * 编写一个程序，找到两个单链表相交的起始节点。
 *
 * 如下面的两个链表：
 */
public class 相交链表 {
   static public class Solution {
       //反转链表，再对比，对比后再反转。
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
                ListNode A = reserve(headA);
                ListNode A2 = A;
                ListNode B = reserve(headB);
                int i = 0;
                while (A2.val == B.val){
                    i++;
                    if(A2==null || B==null){
                        break;
                    }
                   if(A2.next.val == B.next.val){
                       A2 = A2.next;
                       B = B.next;

                   }
                   else{
                       break;
                   }
                }

                if(i==0){
                    return null;
                }
                 A2.next = null;
                return reserve(A);
        }

       /**
        *
        * @param headA
        * @param headB
        * @return
        */
       public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
          ListNode pA = headA;
          ListNode pB = headB;
          while (pA != pB){
              pA = pA == null ? headB : pA.next;
              pB = pB == null ? headA : pB.next;
          }
          return pA;

//           ListNode pA = headA, pB = headB;
//           while (pA != pB) {
//               pA = pA == null ? headB : pA.next;
//               pB = pB == null ? headA : pB.next;
//           }
//           return pA;


       }

        public ListNode reserve(ListNode head){
            if(head.next == null){
                return head;
            }
            ListNode last = reserve(head.next);
            head.next.next = head;
            head.next = null;
            return last;
        }
    }

    public static void main(String[] args) {
        System.out.println(null == null);
        Solution solution  = new Solution();
        MyLinkedList linkA = new MyLinkedList(new int[]{1,2,3,4,5});
//        MyLinkedList linkB = new MyLinkedList(new int[]{5,0,1,8,4,5});
//       ListNode node = solution.getIntersectionNode2(linkA.head.next,linkB.head.next);

        ListNode node2 = solution.reserve(linkA.head);
    }
}
